# Read the solution [Here](https://quastor.org/cracking-the-coding-interview/trees-and-graphs/route-between-nodes)

# Route Between Nodes 

## Cracking The Coding Interview 4.1

<br/>

# Question

You are given a directed graph. You're also given a `start` node and an `end` node.

<br />

Write an algorithm to check whether there is a route between the two nodes.

<br />

<details>
  <summary> Solution</summary>

We can solve this question using any type of graph traversal algorithm. Breadth-First Search or Depth-First Search would both work optimally.

<br />

We start our graph traversal at the `start` node. If we can reach the `end` node, then we return `True`, otherwise `False.`

<br />

Both a BFS and a DFS will take $$O(\lvert V \rvert + \lvert E \rvert)$$ time and $$O(\lvert V \rvert)$$ space.

<br />

We'll be implementing our algorithm with a Depth First Traversal.

<br />

We create a `visited` set that keeps track of which nodes we've already visited in our DFS.

<br />

We implement our DFS recursively, where we first check if the current node is equivalent to the `end` node (the node we're searching for).

<br />

If it is, then we can return `True`.

<br />

Otherwise, we recurse through all the neighbors of the current node and then run a depth first search on each of the neighbors. Of course, we first check to make sure we haven't already visited the neighbor (otherwise we would have an infinite loop in our program).
    
```python
def findRoute(graph, start, end):
    visited = set()
    return dfs(graph, visited, start, end)

  
def dfs(graph, visited, node, end):
    if node == end:
        return True
    
    for neighbor in graph[node]:
        if neighbor in visited:
            continue
        visited.add(neighbor)
        if dfs(graph, visited, neighbor, end):
            return True
    
    return False
```

<a href="https://repl.it/@quastortech/DFS#main.py" target="_blank">Here's a Python 3 REPL with the code.</a>
</details>